package LinkedListPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class LinkedList {
  public static void main(String[] args) {

    SingleLinkedNode n1 = new SingleLinkedNode(1,"1");
    SingleLinkedNode n2 = new SingleLinkedNode(4,"2");
    SingleLinkedNode n3 = new SingleLinkedNode(2,"3");
    SingleLinkedNode n4 = new SingleLinkedNode(10,"3");
    SingleLinkedNode n5 = new SingleLinkedNode(8,"3");
    SingleLinkedNode n6 = new SingleLinkedNode(3,"3");

    /*创建单链表*/
    SingleLinkedList l = new SingleLinkedList();
    System.out.println(l.length());
    l.addByOrder(n1);
    l.addByOrder(n2);
    l.addByOrder(n3);
    l.addByOrder(n4);
    l.addByOrder(n5);
    l.addByOrder(n6);
    l.list();
    System.out.println("==========================");
    SingleLinkedNode n7 = new SingleLinkedNode(3,"10000000");
    l.update(n7);
    /*遍历单链表*/
    l.list();
    System.out.println(l.length());
    System.out.println("==========================");
    l.delete(2);
    l.list();
    System.out.println(l.length());
    System.out.println("==========================");
    l.delete(10);
    l.list();
    System.out.println(l.length());
    System.out.println("==========================");
    /*l.delete(8);
    l.list();
    System.out.println(l.length());
    System.out.println("==========================");
    l.delete(3);
    l.list();
    System.out.println(l.length());
    System.out.println("==========================");
    l.delete(1);
    l.list();
    System.out.println("==========================");
    System.out.println(l.length());*/

    System.out.println(SingLinkedListText.getNumber(l));
  }
}
/*定义节点*/
class SingleLinkedNode{
  public int no;
  public String name;
  public SingleLinkedNode next;

  public SingleLinkedNode() {
  }

  public SingleLinkedNode(int no, String name) {
    this.no = no;
    this.name = name;
  }
  public String toString() {
    return "LinkedListPackage.SingleLinkedNode{no = " + no + ", name = " + name + "}";
  }
}
/*定义单链表*/
class SingleLinkedList{
  /*定义单链表的头节点*/
  private final SingleLinkedNode head = new SingleLinkedNode(0,"");

  public SingleLinkedNode getHeadNode(){
    return this.head;
  }
  /*添加节点*/
  /*1. 找到当前链表的最后一个节点*/
  /*2. 在链表的最后添加节点*/
  /*3. 遍历节点, 找到链表的最后一个节点*/

  public void add(SingleLinkedNode node){
    /*判断传入的节点是否为空*/
    if (node == null){
      return ;
    }
    /*4. 定义临时辅助节点*/
    SingleLinkedNode temp = head;
    /*遍历链表*/
    while(true){
      /*判断临时辅助节点是否指向最后一个*/
      if (temp.next == null){
        break; // 如果临时辅助节点指向链表最后一个节点, 则退出while循环
      }
      temp = temp.next; // 如果临时辅助节点没有指向链表的最后一个节点, 那需要令临时辅助节点向后移动.
    }
    /*5. while循环结束, 此时临时辅助节点指向链表的最后一个节点*/
    /*6. 将节点添加到链表最后即可*/
    temp.next = node;
  }

  /*遍历单链表*/
  public void list(){
    /*1. 判断头节点的下一个节点是否为空*/
    if (head.next == null){
      System.out.println("链表为空");
      return ; // 若头节点的下一个节点为空则链表为空.
    }
    /*2. 定义临时辅助节点*/
    SingleLinkedNode temp = head.next;
    /*3. while循环遍历单链表*/
    while(true){
      /*如果临时辅助节点为空, 则结束while循环*/
      if (temp == null){
        return;
      }
      /*如果临时辅助节点不为空, 则打印节点信息并将临时辅助节点后移*/
      System.out.println(temp);
      temp = temp.next;
    }
  }

  /*按顺序添加节点*/
  public void addByOrder(SingleLinkedNode node) {
    /*1. 判断要添加的节点是否为空*/
    if (node == null) {
      return;
    }
    /*2. 定义临时辅助节点*/
    SingleLinkedNode temp = head;
    /*3. 根据要添加的节点的顺序, 找到要添加的位置*/
    while (true) {
      /*如果临时辅助节点指向链表的最后一个节点, 说明要添加的节点应该插入到链表最后, 停止while*/
        if (temp.next == null){
          temp.next = node;
          return;
        }
        /*如果临时辅助节点.next的no 大于 node.no 则说明node应该插入到temp位置上, 停止while循环*/
        if (temp.next.no > node.no){
          break;
        }
        /*如果临时辅助节点.next的no 等于 node.no 则说明node已经存在, 停止while*/
        if (temp.next.no == node.no){
          System.out.println("节点已经存在");
          return;
        }
        /*令临时辅助节点后移*/
      temp = temp.next;
    }
    /*4. 此时temp.next就是node应该插入的位置*/
    node.next = temp.next;
    temp.next = node;
  }

  /*清空单链表*/
  public void clear(){
    this.head.next = null;
  }

  /*修改单链表的节点值*/
  public void update(SingleLinkedNode node){
    /*1. 判断传进来的节点是否为空 或 单链表是否为空*/
    if (node == null || head.next == null){
      System.out.println("参数无效或链表为空");
      return;
    }
    /*定义临时辅助节点*/
    SingleLinkedNode temp = head.next;
    /*2. while循环找到要修改的节点*/
    while(true){
      /*如果临时辅助节点指向了单链表的最后一个节点, 说明没有修改的节点不在单链表中*/
      if (temp.next == null){
        System.out.println("无符合的节点");
        return ;
      }
      /*如果temp.next.no == node.no 说明找到了要修改的节点, 停止while*/
      if (temp.next.no == node.no){
        break;
      }
      temp = temp.next;
    }
    /*4. 找到了要修改的节点, 令temp.next.name = node.name*/
    temp.next.name = node.name;
  }

  /*删除节点*/
  /*注:
  *   删除节点可能删除在第一个节点, 所有在定义临时辅助节点时, 不能令temp = head.next, 而是定义temp = head*/
  public void delete(int no){
    /*1. 判断单链表是否为空*/
    if (head.next == null){
      System.out.println("链表为空");
      return;
    }
    /*2. 创建临时辅助节点*/
    SingleLinkedNode temp = head;
    /*3. 通过while循环找到要删除的节点*/
    while(true){
      /*判断临时辅助节点是否指向单链表最后*/
      if (temp.next == null){
        System.out.println("无符合的节点");
        return;
      }
      /*判断temp.next.no == no,说明找到了要删除的节点, 停止while*/
      if (temp.next.no == no){
        break;
      }
      /*判断要删除的节点是否为最后一个节点*/
      if (temp.next.no == no && temp.next.next == null){
        temp.next = null;
        return;
      }
      temp =temp.next;
    }
    /*4. 找到了要删除的节点, 直接令temp.next = null即可*/
    temp.next = temp.next.next;
  }

  /*求单链表的长度*/
  public int length(){
    /*定义长度*/
    int length = 0;
    /*判断单链表是否有节点*/
    if (head.next == null){
      return 0;
    }
    /*定义临时辅助节点*/
    SingleLinkedNode temp = head;
    while(true){
      /*判断temp是否指向了单链表最后一个节点*/
      if (temp.next == null){
        break;
      }
      temp = temp.next;
      length ++;
    }
    return length;
  }
}
